import org.omg.CORBA.INTERNAL;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;
import java.util.Scanner;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-04-13
 * Time:19:11
 */
class RandomizedSet {
    int[] array;
    HashMap<Integer, Integer> map;
    int index = -1;
    Random random = new Random();

    public RandomizedSet() {
        array = new int[200010];
        map = new HashMap<>();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        array[++index] = val;
        map.put(val, index);
        return true;
    }

    public boolean remove(int val) {
        if (map.containsKey(val)) {
            int tmp = map.get(val);
            map.remove(val);
            array[tmp] = array[index];
            //index代表最后一个元素,若删掉的就是最后一个元素
            //则无需更改该元素在哈希表中记录的位置;
            //删除的不是最后一个元素则需要修改该元素在哈希表中记录的位置
            if (tmp != index) {
                map.put(array[tmp], tmp);
            }
            index--;
            return true;
        }
        return false;
    }

    public int getRandom() {
        int num = random.nextInt(index + 1);
        return array[num];
    }

    public static void main1(String[] args) {
        RandomizedSet randomizedSet = new RandomizedSet();
        System.out.println(randomizedSet.remove(0));
        System.out.println(randomizedSet.remove(0));
        System.out.println(randomizedSet.insert(0));
        System.out.println(randomizedSet.getRandom());
        System.out.println(randomizedSet.remove(0));
        System.out.println(randomizedSet.insert(0));
    }
    
}
